We present three new quantum algorithms in the quantum query model for\textsc{graph-collision} problem: \begin{itemize} \item an algorithm based ontree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ querieswhere $t$ is the treewidth of the graph; \item an algorithm constructed on aspan program that improves a result by Gavinsky and Ito. The algorithm uses$O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graphparameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex coverof}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\inI}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs thatuses $O(\sqrt{n})$ queries. \end{itemize} We also present an example of apossibly difficult graph $G$ for which all the known graphs fail to solve graphcollision in $O(\sqrt{n} \log^c n)$ queries.
展开▼
机译：在\ textsc {graph-collision}问题的量子查询模型中，我们提出了三种新的量子算法：\ begin {itemize} \ item一种基于树的分解算法，使用$ O \ left（\ sqrt {n} t ^ {\ sfrac {1} {6}} \ right）$查询，其中$ t $是图的树宽； \ item一种在aspan程序上构造的算法，可改善Gavinsky和Ito的结果。该算法使用$ O（\ sqrt {n} + \ sqrt {\ alpha ^ {**}}）$查询，其中$ \ alpha ^ {**}（G）$是由\ [\ alpha ^定义的图形参数{**}（G）：= \ min_ {VC \ text {-顶点覆盖} G} {\ max _ {\ substack {I \ subseteq VC \\ I \ text {-独立集}}}} {\ sum_ {v \ inI} {\ deg {v}}}}; \] \ item一种使用$ O（\ sqrt {n}）$查询的循环图子类算法。 \ end {itemize}我们还提供了一个示例图$ G $，其中所有已知图都无法解决$ O（\ sqrt {n} \ log ^ c n）$查询中的图冲突。
展开▼
